package com.umgsai.wx.backend.test.sort;

import org.apache.commons.lang3.StringUtils;

import java.util.Random;

public class QuickSort {

    public static void main(String[] args) {
        int length = 10;
        int[] array = new int[length];
        /**
         *
         for (int i = 0; i < length; i++) {
         array[i] = new Random().nextInt(100);
         }
         */
        String s = "72  2  33  54  53  12  51  87  49  54";
        String[] s1 = StringUtils.split(s, "  ");

        int index = 0;
        for (String s2 : s1) {
            array[index] = Integer.valueOf(s2);

            index++;
        }

        for (int i : array) {
            System.out.print(i + "  ");
        }

        int left = 0;
        int right = length - 1;

        sort(array, left, right);

        System.out.println("\n快速排序");

        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println();
    }

    public static void sort(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int temp = a[left];
        int i = left;
        int j = right;
        while (i != j) {
            while (i < j && a[j] >= temp) {
                j--;
            }
            if (j > i) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
            while (i < j && a[i] <= temp) {
                i++;
            }
            if (j > i) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        sort(a, left, i - 1);
        sort(a, j + 1, right);
    }

    public static void sort1(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int temp = a[left];
        int i = left;
        int j = right;
        while (i != j) {
            while (i < j && a[j] >= temp) {
                j--;
            }
            if (i < j) {
                // 交换i j
                int x = a[i];
                a[i] = a[j];
                a[j] = x;
            }
            while (i < j && a[i] <= temp) {
                i++;
            }
            if (i < j) {
                // 交换i j
                int x = a[i];
                a[i] = a[j];
                a[j] = x;
            }
        }
        sort1(a, left, i - 1);
        sort1(a, i + 1, right);
    }
}
